package com.tgy.cmp;

import com.tgy.Sort;

import java.util.Objects;

/**
 * @Author: tgy
 * @Date: 2020-10-26 18:04
 */
public class MergeSort01<E> extends Sort<E> {

    private E[] templates;

    @Override
    protected void sort() {

        if (elements.length  <= 1) {
            return;
        }

        if (Objects.isNull(templates)) {
            templates = (E[]) new Object[elements.length >> 1];
        }
        divide(0,elements.length);
    }

    private void divide(int begin, int end) {

        int mid = (begin + end) >> 1;

        if (mid - begin > 1) {

            divide(begin,mid);
        }

        if (end - mid > 1) {

            divide(mid, end);
        }

        /**
         * merge 数组
         */
        merge(begin,mid,end);
    }

    private void merge(int begin, int mid, int end) {

        // 保存左边的数据
        for (int i = begin; i < mid; i++) {

            templates[i - begin] = elements[i];
        }

        int index = begin, tIndex = 0, rIndex = mid,tLength = mid - begin;

        while (tIndex < tLength ) {

            if (rIndex < end && compare(templates[tIndex],elements[rIndex]) > 0) {

                elements[index++] = elements[rIndex++];
            }else {

                elements[index++] = templates[tIndex++];
            }
        }

    }
}
